package com.example.malllocationserver.utils;





import java.util.*;
import java.util.concurrent.ConcurrentLinkedQueue;

public class Dijkstra {
    public static int dijkstra(int[][] graph, int[] path, int len, int vex,int target){
        //dist数组存最短路径
        int[] dist = new int[len];
        //利用hashset代替boolean数组，理论上可提高速度
        Set<Integer> set = new HashSet<>(len);
        set.add(vex);
        //初始化数组
        for (int i = 0; i < len; i++) {
            dist[i] = graph[vex][i];
            path[i]=-1;
        }
        while (set.size() < len) {
            int le = Integer.MAX_VALUE;
            int num = 0;
            for (int i = 0; i < len; i++)
                if (!set.contains(i) && le > dist[i]) {
                    le = dist[i];
                    num = i;
                    break;
                }
            for (int i = 0; i < len; i++)
                if (!set.contains(i)&&dist[num] + graph[num][i]<dist[i]){
                    dist[i] = dist[num] + graph[num][i];
                    path[i]=num;
                }
            set.add(num);
        }
        return   dist[target];
    }

    public static Queue<String> print_road(int[] path,String[] vexs,int len,int u,int v){

        //利用栈实现顺序输出
        Stack<String> stack=new Stack<>();
        Queue<String>  queue=new LinkedList<>();
        String x="";

        stack.push(vexs[v]);
        int p=v;
        while(path[p]!=-1){
            stack.push(vexs[path[p]]);
            p=path[p];
        }
        stack.push(vexs[u]);
        while(!stack.empty()){
            x=stack.pop();
            queue.offer(x);
        }

        return queue;
    }
}
